|
In automata theory, a permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states. Formally, a deterministic finite automaton may be defined by the tuple (''Q'', Σ, δ, ''q''''0'', ''F''), where ''Q'' is the set of states of the automaton, Σ is the set of input symbols, δ is the transition function that takes a state ''q'' and an input symbol ''x'' to a new state δ(''q'',''x''), ''q''''0'' is the initial state of the automaton, and ''F'' is the set of accepting states (also: final states) of the automaton. is a permutation automaton if and only if, for every two distinct states and in ''Q'' and every input symbol in Σ, δ(''qi'',''x'') ≠ δ(''qj'',''x''). A formal language is p-regular (also: a pure-group language) if it is accepted by a permutation automaton. For example, the set of strings of even length forms a p-regular language: it may be accepted by a permutation automaton with two states in which every transition replaces one state by the other. == Applications == The pure-group languages were the first interesting family of regular languages for which the star height problem was proved to be computable.〔〔Janusz A. Brzozowski: ''Open problems about regular languages'', In: Ronald V. Book, editor, ''Formal language theory—Perspectives and open problems'', pp. 23–47. Academic Press, 1980 ((technical report version) )〕 Another mathematical problem on regular languages is the ''separating words problem'', which asks for the size of a smallest deterministic finite automaton that distinguishes between two given words of length at most ''n'' – by accepting one word and rejecting the other. The known upper bound in the general case is . The problem was later studied for the restriction to permutation automata. In this case, the known upper bound changes to . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Permutation automaton」の詳細全文を読む スポンサード リンク
|